package com.fr.lintcode;

import java.util.ArrayList;
import java.util.List;

public class Q242 {

    /**
     * @param root the root of binary tree
     * @return a lists of linked list
     */
    public List<ListNode> binaryTreeToLists(TreeNode root) {
        // Write your code here
    	List<ListNode> rs = new ArrayList<>();
    	if(root == null) {
    		return rs;
    	}
    	ListNode head = null;
    	ListNode ln = null;
    	List<TreeNode> list = new ArrayList<>();
    	list.add(root);
    	while(!list.isEmpty()) {
    		List<TreeNode> tmp = new ArrayList<>();
    		for(TreeNode node : list) {
    			if(node.left != null) {
    				tmp.add(node.left);
    			}
    			if(node.right != null) {
    				tmp.add(node.right);
    			}
    			if(head == null) {
    				head = new ListNode(node.val);
    				ln = head;
    				rs.add(head);
    			}else {
    				ListNode l = new ListNode(node.val);
    				ln.next = l;
    				ln = l;
    			}
    		}
    		head = null;
    		list= tmp;
    	}
    	return rs;
    }


}
